package tree.huffmanTree;

import java.util.*;

/**
 * @author czt
 * @version 1.0
 * @since 2025/1/13
 * 构建过程:
 * 1.将统计了出现频率的字符，放入优先级队列
 * 2.每次出队两个频次最低的元素，给他俩找父节点
 * 3.把父节点重新放入队列，重复2～3
 * 4.当队列只剩一个元素时，Huffman数构建完成
 */
public class HuffmanTree {

    static class Node {

        Character ch; // 字符

        int freq; // 频次

        Node left;

        Node right;

        String code;

        public Node(Character ch) {
            this.ch = ch;
        }

        public Node(int freq, Node left, Node right) {
            this.freq = freq;
            this.left = left;
            this.right = right;
        }

        int getFreq() {
            return freq;
        }

        boolean isLeaf() {
            return left == null;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "ch=" + ch +
                    ", freq=" + freq +
                    '}';
        }
    }

    String str;

    Map<Character, Node> map = new HashMap<>();

    public HuffmanTree(String str) {
        this.str = str;
        char[] chars = str.toCharArray();
        for (char c : chars) {
            if (!map.containsKey(c)) {
                map.put(c, new Node(c));
            }
            Node node = map.get(c);
            node.freq++;
        }
        PriorityQueue<Node> queue = new PriorityQueue<>(Comparator.comparingInt(Node::getFreq));
        queue.addAll(map.values());
        while (queue.size() >= 2) {
            Node x = queue.poll();
            Node y = queue.poll();
            int freq = x.freq + y.freq;
            queue.offer(new Node(freq, x, y));
        }
        Node root = queue.poll();
        int sum = dfs(root, new StringBuilder());

    }

    private int dfs(Node node, StringBuilder code) {
        int sum = 0;
        if (node.isLeaf()) {
            // 找到编码
            node.code = code.toString();
            sum = node.freq * code.length();
        } else {
            sum += dfs(node.left, code.append("0"));
            sum += dfs(node.right, code.append("1"));
        }
        if (code.length() > 0) {
            code.deleteCharAt(code.length() - 1);
        }
        return sum;
    }
}
